import java.util.Arrays;

public class LogLogUnit {

    public static void main(String[] args) {
        System.out.println("测试开始");
        //数组的长度
        int N=10;
        //数组每个值的取值范围1-1000
        int V=1000;
        //测试的次数
        int sizeTime=500;
        for(int i=0; i<sizeTime; ++i) {
            int[] arr=randomArr(N,V);
            int[] arr1=copyArr(arr);
            int[] arr2=copyArr(arr);
            int[] arr3=copyArr(arr);
            bubbleSort(arr1);
            insetSort(arr2);
            selectSort(arr3);
            if( !sameArr(arr1,arr2) || !sameArr(arr1,arr3)) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
            }
        }
        System.out.println("测试结束");
    }

    public static int[] randomArr(int N,int V) {
        int [] arr=new int[N];
        for(int i=0; i<N; ++i) {
            arr[i] = (int) (Math.random()*V) + 1;  //生成随机数[1,V]
        }
        return arr;
    }

    public static int[] copyArr(int[] arr) {
        int len = arr.length;
        int[] newArr = new int[len];
        for(int i=0; i<len; ++i) {
            newArr[i] = arr[i];
        }
        return newArr;
    }

    public static boolean sameArr(int[] arr1,int[] arr2) {
        for(int i=0; i<arr1.length; ++i) {
            if(arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void bubbleSort(int[] arr) {
        for(int end = arr.length-1; end >0; --end) {
            boolean flg=true;
            for(int i=0; i<end; ++i) {
                if(arr[i] > arr[i+1]) {
                    swap(arr,i,i+1);
                    flg=false;
                }
            }
            if(flg) {
                break;
            }
        }
    }

    public static void insetSort(int[] arr) {
        for(int i=1; i<arr.length; ++i) {
            //0-i-1 已经有序  继续从i位置开始往前比较进行插入  i位置位j+1
            for(int j=i-1; j>=0; --j) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

    public static void selectSort(int[] arr) {
        for(int i=0; i<arr.length-1; ++i) {
            int minIndex=i; //记录i~n-1的最小值下标
            for(int j=i+1; j<arr.length; ++j) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr,minIndex,i);
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}
